package com.dyz.leetcode;

public class MaximalSquare221 {
    //类似的题目是最大矩形面积
    //第一种解法 暴力
    //第二种解法 动态规划 dp[i][j] = min(min(dp[i-1][j-1], dp[i][j-1]), min[i-1][j])+1
    public int maximalSquare(char[][] matrix) {
        if(matrix==null||matrix.length==0||matrix[0].length==0){return 0;}

        //base case
        //每一行最大面积就是本身，每一列最大面积就是它本身
        int rows = matrix.length;
        int colums = matrix[0].length;
        int[][] dp = new int[rows][colums];
        //状态转移
        int maxlen =0;
        for(int i=0; i<rows; i++){
            if(matrix[i][0]=='1'){maxlen=1;}
            dp[i][0]=Integer.parseInt(String.valueOf(matrix[i][0]));
        }

        for(int i=0;i<colums;i++){
            if(matrix[0][i]=='1'){maxlen=1; }
            dp[0][i] = Integer.parseInt(String.valueOf(matrix[0][i]));
        }

        for(int i=1;i<rows; i++){
            for(int j=1; j<colums;j++){
                if(matrix[i][j]=='1'){
                    dp[i][j] = Math.min(Math.min(dp[i-1][j-1], dp[i][j-1]), dp[i-1][j])+1;
                    maxlen = Math.max(maxlen, dp[i][j]);
                }
            }
        }
        return maxlen*maxlen;
    }

    public static void main(String[] args) {
        char[][] matrix = new char[][]{{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'}};
        int i = new MaximalSquare221().maximalSquare(matrix);
        System.out.println(i);
    }
}
